平成30年春期 応用情報 午前 問6
異なる$ n個のデータが昇順に整列された表がある。この表を$ m個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，$ mは十分に大きく，$ nは$ mの倍数とし，目的のデータは必ず表の中に存在するものとする。 ア $ m+\frac{n}{m}
イ $ \frac{m}{2} + \frac{n}{2m}
ウ $ \frac{n}{m}
エ $ \frac{n}{2m}